<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Битовые операции, множества, динамика</h2>
<ol>
  <li>Битовые операции</li>
  <ol>
    <li>Объединение, пересечение, разность, i-й элемент, является ли A подмножеством B</li>
    <li>Количество бит в числе за O(1), старший бит за O(1)</li>
    <li>Перевернуть битовую записать числа как строку за O(1)</li>
  </ol></li>
  <li>Надмножества и подмножества</li>
  <ol>
    <li>Перебор всех подмножеств циклом for (b = A; b > 0; b--, b &amp;= A)</li>
    <li>Перебор всех надмножеств циклом for (b = A; b < 2<sup>n</sup>; b++, b |= A)</li>
    <li>Почему два вложенных цикла работают за O(3<sup>n</sup>)?</li>
  </ol></li>
  <li>Динамика по подмножествам</li>
  <ol>
    <li>Гамильтоновы путь и цикл</li>
    <ol>
      <li>Путь за O(2<sup>n</sup>n<sup>2</sup>)</li>
      <li>Цикл за O(2<sup>n</sup>n<sup>2</sup>)</li>
      <li>Оптимизируем память с O(2<sup>n</sup>n) до O(2<sup>n</sup>)</li>
    </ol></li>
    <li>Количество подклик в графе</li>
    <ol>
      <li>За O(2<sup>n</sup>n<sup>2</sup>)</li>
      <li>За O(2<sup>n</sup>n) (битовые операции)</li>
      <li>За O(2<sup>n</sup>) (два решения = рекурсивный перебор или динамика)</li>
    </ol></li>
    <li>Есть 3n человек, некоторые дружат с некоторыми (a-b &rarr; b-a). Разбить всех на команды по 3 человека так, чтобы внутри команды все дружили.</li>
    <ol>
      <li>За O(2<sup>n</sup>n<sup>3</sup>)</li>
      <li>За O(2<sup>n</sup>n<sup>2</sup>)</li>
    </ol></li>
    <li>Есть n лекций. Некоторые лекции нельзя читать до других. У лекций есть сложность и полезность. Выбрать курс так, чтобы полезность была максимальна, а сложность не больше A.</li>
    <ol>
      <li>За O(2<sup>n</sup>n<sup>2</sup>)</li>
      <li>За O(2<sup>n</sup>n)</li>
      <li>За O(2<sup>n</sup>)</li>
    </ol></li>
    <li>Найти совершненное паросочетание</li>
    <ol>
      <li>За O(2<sup>n</sup>n<sup>2</sup>)</li>
      <li>За O(2<sup>n</sup>n)</li>
    </ol></li>
  </ol></li>
</ol>
